package interview;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.concurrent.ConcurrentHashMap;

public class lc907 {
    public static void main(String[] args) {
        System.out.println(sumSubarrayMins(new int[]{3,1,2,4}));
    }
    //暴力超时
    public static int sumSubarrayMins1(int[] arr) {
        long ans = 0;
        for (int i = 0; i < arr.length; i++) {
            int minValue = arr[i];
            for (int j = i; j < arr.length; j++) {
                minValue = Math.min(minValue, arr[j]);
                ans = (ans + minValue) % (1000000007);
            }
        }
        return (int)ans;
    }

    //单调栈，找左右比当前元素小的元素，栈里面存放下标
    public static int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]){
                stack.pop();
            }
        }
        return n;
    }
}
